Otherware/Otherware_1_SB_Development.iso/mac/misc/biology/logolife.cpt/Logo Life/Logo Life TEXT

Text File | 1992-07-27 | 21.3 KB | 514 lines

Logo Life

By Tim Endres

Release 1.0


Tim Endres, ICE Engineering, Inc.
8840 Main Street, Whitmore Lake, MI  48189
Internet:  [e-mail]


Table Of Contents
Introduction    1
Basics    1
Turtles    1
Turtle Populations    2
Definitions    3
Turles and Logo Expressions    3
Population Window    3
Getting Started    3
Installing Logo Life    3
Running Logo Life    3
The Population Window    4
Evolution    5
Your First Generation    5
Turtle Fitness Selection    5
Population Evolution    5
Turtle Features    6
Turtles And The ClipBoard    6
Zooming In On A Turtle's Figure    6
Doping Turtles    6
Mutating Turtles    7
Printing Turtles    7
Saving Turtles    7
Advanced    8
Genetic Algorithms and Genetic Programming    8
Logo Expressions and Programming    8
Creating Your Own Turtles    9
Further Study    10


Introduction

Logo Life is an application that combines the concepts of Genetic
Programming and Logo Graphics. From this combination comes a
fascinating and entertaining hybrid that not only produces stunning
graphics, but teaches a great deal about programming, genetics, and the
basic principles of Artificial Life.

Logo is the graphical language used frequently to teach the basic principles
of programming. The concept is very simple ╨ you are in control of a turtle
that has a pen that can be dropped to draw and lifted to not draw, and you
are able to give the turtle simple commands to move forward, turn right
and turn left. With this extremely simple set of instructions, one is capable
of creating a vast combination of graphical images, and this is
accomplished with simple algorithms that are recursive in nature.

Genetic programming languages are an upshot of the splendid work
inspired by John Holland involving Genetic Algorithms. John Holland's
work took a simple example from nature, one of our universe's most
impressive creations, and applied it to adaptive computer algorithms
involving search and optimization. Holland's work involved mapping a
problem representation into a binary string, or chromosome, and using
genetic and evolutionary principles of fitness proportionate selection for
reproduction, with random crossover and mutation, to search enormous
solution spaces efficiently.

Genetic programming languages apply the same principles of fitness
proportionate selection for reproduction and random ccrossover and
mutation, but the chromosome in this case is an expression tree, not a bit
string as in traditional GAs. The expression tree in Logo Life is a syntax
that drives the Logo Turtle. The fitness each logo expression expression is
determined by you, the driver of Logo Life.

You will find that Logo Life is very simple, but has very subtle depths. You
will also find it difficult to stop evolving new logo turtles! Generation after
generation. In fact, once you are convinced that Logo Life has nothing more
to offer, it will astound you with an image you did not anticipate, and a new
line of creativity will evolve. Enjoy

Basics

Turtles

Logo Life is about turtles. Logo Turtles. Logo turtles are special turtles that
know how to draw in the sand. They spend long leisurely days on the beach,
tanning their shells and soaking up rays with their cheap sunglasses on.
Turtles, being the laid back bunch that they are, will only perform a few
tricks when it comes to making lines in the sand. In fact, the only tricks
that these turtles have up their sleeve are:

* Turtles can lift their stick (so they make no tracks) or drop their stick (so
they make tracks)

* Turtles can move forward a specific number of steps.

* Turtles can turn left and right a specific number of degrees.

That's all a poor turtle can do. But don't let them fool you! They can draw
things you wouldn't believe.

In a later chapter we discuss these commands in detail, and describe how
you can write your own turtle logo programs.


Turtle Populations

Turtles live in small populations, whose number depend upon your screen
size. Generally the number of turtles in your population is 24. Each turtle in
the population has its own sand in which to draw.

Each turtle will draw its figure in the sand during its lifetime, or in a
single generation. After each turtle draws its figure, they will display them
to you, and you will decide which turtles are fit to reproduce for the next
generation of turtles.

Once you have selected the most fit turtles, they will reproduce in a fitness
proportionate fashion1 (the best turtles randomly mate, while the least fit
turtles are left out) to create a new population of turtles that will replace the
older population. As with natural genetics, some of the turtles in the new
population will be virtually exact duplicates of their parents, while others
will combine the features of their parents to create a new figure.

Generation after generation, you will select the turtles that exhibit the type
of figure drawing behaviour that you seek, and the population will evolve
over time to create some of the most fascinating figures you have ever seen,
and possibly teach you things about the logo programming language you
had not considered.


Definitions

Turles and Logo Expressions

A Logo Life turtle, like its logo counterpart is in actuality a graphical
cursor. It has a very simple state, namely a coordinate position, a direction
in which it is pointed, and a stick that is either up or down.

The turle's location is quite immaterial, since all of the turtle's commands
operate in a relative fashion, such as move forward 2 steps. Further, no
matter how large the turle's figure gets, nor how far it may wander from
its original starting point, the figure will be scaled and translated to be
centered within your visual display.

The direction in which the turtle is facing is again immaterial from the
turtle's point of view. Everything that the turtle does is relative to the
direction it is currently facing. This is why the turtle's language only
allows for commands like turn right 10 degrees, and does not allow for
commands such as turn to 48 degrees due north.

The one state in which the turtle is most interested is the state of the stick.
When the stick is down, the turtle is making figures in the sand. When the
stick is up, the turtle still moves, but does not make any figures in the sand.

Population Window

The population window displays a generation of turtles' figures. Each
turtle's figure is drawn for you in a small square in the Population
Window. The population window can also display an enlarged view of any
one of the turtles' figures.

The population window is your view of the evolving world of the logo turtles.
In each successive generation, you will be shown the turtle's figures and
will determine which turtles will be involved in the evolution of the next
generation of turtles.


Getting Started

Installing Logo Life

To install Logo Life, simply copy the Logo Life folder to your hard disk. You
do this by dragging the Logo Life folder to your hard disk icon. Once the
folder is copied to your hard drive, you are ready to go.

Running Logo Life

Running Logo Life is as simple as installing it. You simply open the Logo
Life folder that you copied to your hard drive by double clicking on it. Inside
this folder you will find the Logo Life application. Double click on the Logo
Life application icon. This will cause the Logo Life program to be lauched
and the Logo Life menus to be displayed in the menu bar.

To begin a new population of Logo Life turtles, you must select the New
Population item in the File menu. This will open a new population window,
in which turtles will be randomly created, and each turtle will display its
figure in a small square.

It will take some time, depending on the complexity of each turtle's
algorithm, to draw all of the figures for the entire population, so please be
patient while this is done. You may click in other applications during this
time, and Logo Life will compute the figures in the background.


The Population Window

The Population Window is a non-scrollable, fixed size window which will
display turtle figures. When a new population is evolved, the window will
display all of the population's figures in small rectangles arranged in rows
and columns.

You may click on a particular figure to make it's turtle the currently
selected turtle. The selected turtle is identified by inverting the figure of the
turtle to distinguish it from the other turtles.

A selected turtle may have several operations performed upon it. For
instance, you may have the turtle's figure blown up to be displayed in the
full contents of the population window. This allows you to inspect the finer
details of the turtle's figure. You can also print a turtle's figure, save its
figure and its corresponding algorithm to a file, or copy a turtle and paste it
into another turtle's square (competition and survival). You may also dope
a selected turtle with another turtle's algorithm that was earlier saved to a
file, and finally, you may mutate a selected turtle to change its algorithm,
and thus, its figure.

Notice that there is a thick lined square outside the figure of all of the
turtles. This is an indication that this turtle is currently chosen to
participate in the reproduction of the next generation of turtles. If the thick
square is not displayed around a turtle, then it will not be chosen for
reproduction to create the next generation of turtles.

You can chose all turtles for participation in the next generation using the
Chose All Turtles command in the File menu. You may chose none of the
turtles for participation in the next generation by selecting the Chose No
Turtles command in the File menu.


Evolution

Your First Generation

When your first generation of turtles is displayed, you may notice that
overall the figures are not that impressive. This is, of course, to be expected,
since the turtles are created in a completely random fashion. In fact, if any
of the turtles shows any signs of interesting behaviour, this is merely a low
probability event and should be considered a blessing.

However, do not be discouraged. As you begin to selectively choose turtles
for reproduction and evolution, you will see dramatic jumps in the level of
sophistication of your turtles. For each new generation of turtles does not
have to re-learn the complexities of their parents, they are fortunate enough
to inherit them from the genetic constituency of their parents. In fact, as
new figures appear in succeeding generations, you will begin to notice the
parts that they inherited from their parents, and even begin to identify
different turtles as being siblings!

Once you have evaluated the figures of your first generation of turtles, you
will certainly wish to evolve a new generation of turtles to see the
evolutionary process in full swing. But first, you must decide which turtles
will be fortunate enough to participate in the reproduction of this new
generation of more elite figure drawing turtles.

Turtle Fitness Selection

Before evolving a new generation of turtles, it is beneficial to select only the
turtles you are interested in persuing. If you were to simply allow all of the
turtles to evolve equally, then the population as a whole would simply
wander genetically, with a low probability of producing any particular type
of order upon the algorithms that define how the turtles actually draw their
figures. Thus, you must select those that you wish to persue and those that
you do not. This allows you to focus in on particular traits in the turtles,
and to persue these traits in successive generations.

You may change the fitness of a turtle for reproduction by using an option-
click. Clicking on a turtle's figure while holding down the option key will
causing the turtle's fitness to be toggled. Thus, if the turtle was originally
fit (had a thick square around its figure) it will be made unfit and will not be
selected for reproduction. Accordingly, if the turtle was originally unfit (did
not have a thick square around its figure), then it would be identified as fit
and the thick square border drawn around it.

Population Evolution

Once you have chosen the turtles that are fit to be reproduced, you can
evolve your next generation of turtles. To accomplish this task, select the
Evolve Population item in the File menu.

This command will clear the population window's display, evolve the next
generation of turtles, and begin displaying their figures in their respective
squares. Again, the amount of time needed to perform this drawing
depends upon the complexity of each turtle's algorithm.


Turtle Features

Turtles And The ClipBoard

You may copy and paste turtles to and from the clipboard just like any other
Macintosh data. When a turtle is copied to the clipboard, using the
Copy╩command in the Edit menu, both textual and graphical data are
placed on the clipboard.

The textual data (data type TEXT) will contain the logo algorithm used by
the turtle to draw its figure. This data can then be pasted into any text
editor, or other application that utilizes text. Further, this textual data may
be pasted back into any selected turtle to replace its algorithm (and thus
figure) with that represented by the algorithm on the clipboard.

The graphical data contains a standard Macintosh picture (data type PICT)
that can be pasted into any application that accepts PICT data. This allows
you to paste a turtle's figure into graphical documents and as figures in
textual documents.

Zooming In On A Turtle's Figure

To display a turtle's figure in the full area of the population window (to blow
it up), sinply double click on the turtle's figure, or select the turtle's figure
by clicking on it once, and select the Zoom Selection command in the File
menu.

This will cause the turtle to display its figure full size in the contents of the
population window. To return to viewing the entire population, simply click
anywhere within the contents of the window, and the entire population will
be displayed once again.

Doping Turtles

Doping a turtle means to replace its algorithm with another. This causes
the turtle to display a figure that you select. This can be accomplished with
the algorithm from a previously saved turtle, or it could be an algorithm
that you have copied and modified, or it could be an algorithm that you have
manufactured yourself using the Logo language.

Doping a turtle from a previously saved turtle is accomplished via the Dope
Selection command in the File menu. This command is only highlighted
when a turtle is selected. When you select the command, the Standard Get
File Dialog will be displayed asking you to select a file which contains a
previously saved turtle. Once you select a file, this file's turtle algorithm
will replace the algorithm of the selected turtle, and the new figure will be
drawn in the selected turtle's square.

Doping a turtle from an algorithm in textual form is accomplished via the
Paste command in the Edit menu. When the Paste command is selected, it
will look on the Macintosh Clipboard for textual data (data type TEXT). If
textual data is found, it is assumed to be an expression using the logo
language. If this turns out to be true, and the algorithm is syntactically
correct (meaning there are no mistakes in the expression), then the
currently selected turtle will have its algorithm replaced with the
algorithm from the clipboard and a new figure will be drawn for the turtle.

Mutating Turtles

Mutating turtles involves randomly generating a logo expression and then
randomly splicing this expression into the algorithm of the turtle. This can
have a wide range of effects, from no visual difference, to profound visual
change including no display at all.

Mutating a turtle is accomplished by selecting the turtle's figure, then
selecting the Mutate Selection item in the File menu. This will cause the
mutation to be made to the selected turtle, and its new figure to be displayed
in its square.

Mutation is usually used when a population appears to be stuck in a
particular feature set and it is proving difficult to move the population into
any new directions without the injection of some random figures.


Printing Turtles

You may print a turtle's figure to any Apple supported printer. This is done
by selecting the desired turtle's figure and selecting the Print Selection
command from the File menu.

For laser printers, Logo Life will include the QuickDraw Picture Comment
that causes the printer to draw lines as thinly as possible. This will improve
the resolution of your printed figures to whatever is available from the
printer.

Saving Turtles

You may save turtles to a file. This will cause two things to be saved. In the
data fork of the file, the text that represents the logo algorithm used to draw
the turtle's figure will be saved. This allows you to use any TEXT editor
available to you to view the turtle's algorithm. You may even modify the
algorithm to create new figures, or to improve upon an existing figure.

In the resource fork of the turtle file (where dialogs and such are stored),
the picture (data type PICT) that represents the turtle's figure will be
stored. This allows you to open the figure and paste it into applications that
are able to use the PICT data, such as graphics programs.


Advanced

Genetic Algorithms and Genetic Programming

Genetic algorithms are fast becoming a hot area of computer science
research. Propelled into popularity by the pioneering work of John Holland
at the University of Michigan in the 1970's, genetic algorithms have been
successfully utilized in problem areas previously thought intractible.
The concept of genetic algorithms is very simple. A problem is mapped into
a chromosome expression and the principals of fitness proportionate
selection and crossover mating are implemented to successively evolve
populations of proposed solutions that over time evolve to an acceptable
solution to a problem.

Genetic programming takes the genetic algorithm one step further, by
mapping the problem such that we are looking for an algorithm. The
desired algorithm is then evolved by generating random algorithms and
successively reproducing them using the genetic principles of fitness
proportionate selection and crossover mating.

The advantage of evolving logo algorithms is that the results are visual and
can show inheritence is a striking way. This allows a student of genetic
algorithms to get a visual sense of how the algorithms evolve over time, and
in what ways they evolve.


Logo Expressions and Programming

Logo is a graphical programming language. It has been around for many
years, and is currently popular for teaching simple programming
principles to students. It is exceptionally good for this task, since the
concept of the turtle is much easier to grasp than that of a CPU, and the
results of the programs are visual, providing good feedback and motivation.
Logo Life takes the logo language and reduces it to an extremely simple
subset. The reasons for this are many, but the primary reason is that the
reduction is required to make the genetic algorithm feasible.

The Logo Life programming language can be most simple summed up in
the following manner:
algorithm    =>    expr
expr        =>    ( terminal )
            or
            ( function expr_list )
expr_list    =>    expr ...

terminal    =>    One of the following:

FWD_1, FWD_2, FWD_3, FWD_5, FWD_10,
FWD_50, FWD_100
These commands move the turtle the number of specified
steps forward from its current position in the direction it is
facing. If its stick is down, drawing occurs as the turtle
moves.

LEFT_1, LEFT_2, LEFT_3, LEFT_5, LEFT_10,
LEFT_15, LEFT_45, LEFT_90
These commands turn the turtle the specified number of
degrees to the left from its current direction.

RIGHT_1, RIGHT_2, RIGHT_3, RIGHT_5, RIGHT_10,
RIGHT_15, RIGHT_45, RIGHT_90
These commands turn the turtle the specified number of
degrees to the right from its current direction.

function    =>    One of the following:

BLOCK
This command executes the expressions in its expression
list.

REPEAT_2, REPEAT_3, REPEAT_5, REPEAT_10,
REPEAT_50, REPEAT_100
These commands repeat the expressions in their expression
list the specified number of times.

IF_PEN_UP, IF_PEN_DOWN
These two commands execute the first expression in their
expression list if true, otherwise they ecxecute the second
expression.


Creating Your Own Turtles

You can use any Macintosh text editor to create a turtle logo expression and
paste the expression into a population to help with its evolution, or to
explore new evolutionary paths.

For example, you might type in the following program and paste it into a
turtle's square that you select in a population window:

( REPEAT_2 ( REPEAT_2 ( FWD_100 ) (RIGHT_90 ) ) )

The logo expression above would draw a square with sides 100 steps long.
You might also try this expression:

( REPEAT_5
( FWD_100 )
( RIGHT_45 )
( RIGHT_5 )
( RIGHT_10 )
( RIGHT_10 )
( RIGHT_2 )
)

Or you might try this one:

( REPEAT_100
( FWD_100 )
( RIGHT_90 )
( RIGHT_10 )
( RIGHT_10 )
( RIGHT_5 )
( RIGHT_3 )
)

Further Study

There are many good books on both logo and genetic algorithms.
The following books have proved useful for me:

Turtle Geometry by Harold Abelson and Andrea A. diSessa. Published by
The MIT Press, Cambridge, Massachusetts. ISBN 0-262-01063-1.

Adaptation In Natural And Artificial Systems by John Holland. Published
by The MIT Press, Cambridge, Massachusetts. ISBN 0-262-58111-6.

Genetic Algorithms in Search, Optimization and Machine Learning by
David Goldberg. Published by Addison Wesley, Rading, Massachusetts.
ISBN 0-201-15767-5.